/*
给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。
可以按 任意顺序 返回答案。
*/
#include <vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    vector<TreeNode*> generateTrees(int left, int right) {
        if (left > right) {
            return {nullptr};
        }

        vector<TreeNode*> res;

        // 依次将区间内的每个数字i作为根节点
        for (int i = left; i <= right; i++) {
            // 所有可行的左子树的集合
            vector<TreeNode*> leftTrees = generateTrees(left, i - 1);
            // 所有可行的右子树的集合
            vector<TreeNode*> rightTrees = generateTrees(i + 1, right);

            // 从左子树集合选出一颗左子树，从右子树集合中选出一颗右子树，拼接到根节点上
            for (auto& left : leftTrees) {
                for (auto& right : rightTrees) {
                    TreeNode* node = new TreeNode(i, left, right);
                    res.emplace_back(node);
                }
            }
        }

        return res;
    }
    vector<TreeNode*> generateTrees(int n) {
        return generateTrees(1, n);
    }
};

int main() {
    return 0;
}